googologywikiaorg-20200223-history
User blog:Syst3ms/Using cellular automata to generate a potentially uncomputable function
Sup. Formal definition of a cellular automaton We define a cellular automaton \(A\) as a 5-tuple \((d,\Sigma,\Delta,r,s)\) : *\(d \in \mathbb{N}\) is the dimension of the automaton *\(\Sigma \in \mathcal{P}(\mathbb{N})\) is its alphabet *\(\Delta \in \mathcal{P}(\mathbb{N}^d)\) is its neighbourhood. It describes which neighbouring cells the local rule accounts for. *\(r : \mathcal{P}(\Sigma^{\|\Delta\|}) \to \Sigma\) is the automaton's local rule. It describes how cells are born and die. *\(\sigma : \mathbb{N}^d \to \Sigma\) is the state function of the automaton. Simply put, it gives the state of a cell at a given coordinate. Related functions \(U : \Sigma^{\mathbb{N}^d} \to \Sigma^{\mathbb{N}^d}\) is the state update function. It updates the state function to return the state of every cell, updated using the local rule. It's defined as \(U(\sigma) = \sigma'\text{ such that }\forall p\in\mathbb{N}^d(\sigma'(p) = r(\{\sigma(n+p)|n \in \Delta\}))\). \(n+p\) corresponds to adding tuples of the same length, which is defined as : \(\forall n>0\wedge n\leq m((A+B)n = An+Bn)\), where A and B are \(m\)-tuples and \(n\) corresponds to the \(n\)th element of the tuple, starting at 1. The updated state function returns what the local rule returns when given all the cells in the neighbourhood of a given coordinate. If we let \(\mathbb{A}\) denote the set of all possible automata, and any given automata \(A = (d,\Sigma,\Delta,r,\sigma)\), then we define the step function \(S : \mathbb{A} \to \mathbb{A}\), defined as \(S(A) = (d,\Sigma,\Delta,r,U(\sigma))\). We will use \(S(n,A)\) as a shorthand for function iteration \(S^n(A)\). We define the population function \(P : \Sigma^{\mathbb{N}^d} \to \mathbb{N}\) as \(P(\sigma) = \|\{a \in \mathbb{N}^d : \sigma(a)>0\}\|\). This gives the number of living cells. We then define two related functions : the stable time function \(T : \mathbb{A} \to \mathbb{N}\) and the '''cycle '''function \(C : \mathbb{A} \to \mathbb{N}\). They are defined as such, where \(i,j,k \in \mathbb{N}\) : \(T(A) = \min\{i : \exists j\forall k(P(S(i,A)) = P(S(i+jk,A)))\} \\ C(A) = \min\{j : \exists i \forall k(P(S(i,A)) = P(S(i+jk,A)))\}\) The stable time function gives the smallest time at which the automaton enters a predictable cycle, and the cycle function the length of that cycle. Note that these values do not exist for all automata, since some starting configuration exhibit unbounded population growth, such as the Glider Gun Gosper Glider Gun. Defining Conway's Game of Life and \(\Lambda(n)\) The traditional rule of GoL is that a cell is born when there are 3 living cells around a dead cell, and that a cell survives if there are 2 or 3 living cells around it. It uses the Moore neighbourhood, a 3x3 square. First of all, \(d = 2 \\ \Sigma = \{0,1\} \\ \Delta = \{(-1,-1),(-1,0),(-1,1),(0,-1),(0,0),(0,1),(1,-1),(1,0),(1,1)\}\). Now we need to define the local rule : \(r© = \begin{cases} 1 & (\sum\limits^{9}_{n=1} (cn) - c5 = 3) \vee (\sum\limits^{9}_{n=1} (cn) = 3) \\ 0 & \text{otherwise} \end{cases}\) We will denote the automaton with these parameters by \(L\). How the state function is defined will determine the starting configuration of the automaton. For example, a state function that returns 1 for inputs \((0,0),(0,1),(1,0),(1,1)\) and 0 for all other inputs will correspond to starting off with a 2x2 square, a stable structure called a block. Therefore, our BB analogue will return the maximum time taken to stabilize for all starting configurations with a given population. Since the inital state can change, the notation \(A_\sigma\) will describe an automaton \(A\) with state function \(\sigma\). We can finally define the '''Life '''function \(\Lambda : \mathbb{N} \to \mathbb{N}\) as \(\Lambda(n) = \max\{T(L_\sigma) | \sigma \in \Sigma^{\mathbb{N}^d} \wedge P(\sigma) = n\}\). Function analysis and lower bounds It is pretty easy to prove that \(\Lambda(n)\) is monotonic (Theorem 1) : Proof 1 : If \(\Lambda(n) = b\) for some \(n\), then \(\Lambda(n+1) \geq b\), since it is always possible to add an isolated cell that immediately dies, which does not change the stable time \(b\). Objects which take a long time to stabilize are known as methuselahs in the Game of Life community, and methuselah research provides us lower bounds for \(\Lambda(n)\). Here are known values and lower bounds : \(\Lambda(0) = 0 \\ \Lambda(1) = 1 \\ \Lambda(2) = 1 \\ \Lambda(3) = 2 \\ \Lambda(4) = 11 \\ \Lambda(5) = 1105 \\ \Lambda(6) = 1105 \\ \Lambda(7) = 5206 \\ \Lambda(8) = 7468 \\ \Lambda(9) = 17410 \\ \Lambda(10) \geq 17425 \\ \Lambda(11) \geq 23334 \\ \Lambda(12) \geq 23334 \\ \Lambda(13) \geq 29126 \\ \Lambda(14) \geq 29126 \\ \Lambda(15) \geq 32829 \\ \Lambda(16) \geq 47487 \\ \) The methuselah lasting for 47487 generations is currently the longest known. Notes : When the value stays the same for successive numbers, it just means no further improvement has been found using one more cell. Thus, the value stays the same because of Theorem 1. I started only putting \(\geq\) after 9 because it is not confirmed that the corresponding methuselahs are the best possible Thanks to AxiomaticSystem#3625 for telling me that the bounds below 10 are exact. Uncomputability of \(\Lambda\) It was proven in 1982 by John Conway that Game of Life is capable of computing anything that a Turing machine can compute. This leads me to assume that proving whether a given starting configuration is going to stabilize is equivalent to the halting problem, making \(\Lambda\) an uncomputable function. However, I am not sure of this, and I would be glad to receive any additional info on whether this is the case, and whether it can be shown \(\Lambda\) outgrows all computable functions. Category:Blog posts